#include<cstdio>
#include<cstring>
const int maxn=12;
const int INF=0xfffffff;
int dp[60000][maxn],p[maxn];
int fac[13],s[13];
int g[maxn][maxn];
int n,m;
void init()
{
	fac[0]=1;
	for(int i=1;i<=10;i++)
		fac[i]=fac[i-1]*3;
}
int hash(int a[])
{
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=fac[i-1]*a[i];
	return ans;
}
bool code(int s,int *a)
{
	bool f=true;
	for(int i=1;i<=n;i++)
	{
		a[i]=s%3;
		s/=3;
		if(a[i]==0)f=false;
	}
	return f;
}
int min(int x,int y)
{
	return x<y?x:y;
}
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
void merge(int a,int b)
{
	int x=find(a);int y=find(b);
	p[x]=y;
}
int main()
{
	init();
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)p[i]=i;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i==j)g[i][j]=0;
				else g[i][j]=INF;
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(c<g[a][b])g[a][b]=g[b][a]=c;
			merge(a,b);
		}
		for(int i=1;i<=fac[n]-1;i++)
			for(int j=1;j<=n;j++)
				dp[i][j]=INF;
		memset(dp[0],0,sizeof(dp[0]));
		int ans=INF;
		for(int i=1;i<=fac[n]-1;i++)
			for(int j=1;j<=n;j++)
			{
				bool f=code(i,s);
				if(s[j]>0)
				{
					if(i==fac[j-1])
						dp[i][j]=0;
					else
					{
						s[j]--;
						int state=hash(s);
						for(int k=1;k<=n;k++)
							if(j!=k&&s[k]>0)													dp[i][j]=min(dp[i][j],dp[state][k]+g[k][j]);
					
					}
				}
				if(f)ans=min(ans,dp[i][j]);
			}
		int cnt=0;
		for(int i=1;i<=n;i++)
			if(p[i]==i)cnt++;
		if(cnt==1&&ans<INF)printf("%d\n",ans);
		else printf("-1\n");
	}
	return 0;
}


	

